import { MGraph, VNode } from "./Graph.type";

function DijKstra(g: MGraph<number>, v: VNode<number>) {
	let distanceArr: Array<number>;
	let orderedArr: Array<number>;
	// let markArr: Array<number>;// </number>
	let min: number = Infinity;
	let temp: number = 0;
	let tempArr: Array<number>; //</number>
	// orderedArr = new Array(g.n);
	for (let i: number = 0, tempArr = g.edge[0]; i < g.n; i++) {
		distanceArr[i] = tempArr[i];
	}

	orderedArr.push(0);

	for (let i: number = 1; i < g.n; i++) {
		min = Infinity;
		for (let j: number = 1; j < g.n; j++) {
			if (orderedArr[i] == 0 && distanceArr[i] < min) {
				min = distanceArr[i];
				temp = i;
			}
		}
		orderedArr.push(temp);
		tempArr = g.edge[temp];

		for (let j: number = 1; j < g.n; j++) {
			if (orderedArr[i] == 0 && distanceArr[i] > min + tempArr[i]) {
				distanceArr[i] = min + tempArr[i];
			}
		}
	}

}

/*
初始化：
起点值初始化（past=NULL，dist=0，visit=1）
其他节点值初始化（past=NULL，dist=无穷，visit=0）
起点入队
循环1：直到队列中没有元素
   从队伍中输出一个节点作为当前节点
   循环2：访问与当前节点连通但是【没有被访问过】的节点（visit=0的节点）
      将即将访问的节点记为正在访问的状态
      将即将访问的节点的状态更新（past=当前节点，dist=即将访问的节点到当前节点的距离，visit=1）
      即将访问的节点入队
   将当前节点的visit记为2（因为与它连接的所有节点都被访问过）


初始化：
所有节点值初始化（past=NULL，dist=无穷，visit=0）
递归DFS（当前节点）
  当前路径正在访问当前节点（visit=1）
  对与当前节点连通的所有【没有被访问过】的节点
      改变即将访问的节点的状态（past为当前节点，dist为即将访问的节点到当前节点的距离）
      DFS（即将访问的节点）
      【如果有环路，这里还要加一步：如果当前节点的visit不是2，就把visit设为0，否则被访问过一次就再也访问不了了】
  将当前节点的visit记为2（因为与它连接的所有节点都被访问过）


初始化：
起点初始化（dist=0，past=NULL，visit=1）
其他节点初始化（dist=无穷，past=起点，visit=0）
循环：对于所有节点
  循环：对于所有【不确定到起点最短距离】的节点，找出距离起点最近的节点并记录距离(与起点直接相连的点)
  更新找出的节点的状态（visit=1）
  循环：对于所有【不确定到起点最短距离】的节点
    计算它到刚才找出的节点的距离
    如果节点经过刚才找出的节点到起点的距离小于节点直接到达起点的距离
      更新节点的状态（dist=找出的节点的dist+找出的节点到该节点的距离，past=找出的节点）

*/